package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.StackProblem;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * 滑动窗口 单调队列
 * @author tzp
 * @since 2020/10/15
 */
public class LC239 implements StackProblem {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] result = new int[nums.length - k + 1];
        LinkedList<Integer> deque = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            putInDDQ(deque, nums[i]);
            if (i - k >= 0 && nums[i - k] == deque.getFirst()) {
                deque.removeFirst();
            }
            if (i - k >= -1) {
                result[i - k + 1] = deque.getFirst();
            }
        }
        return result;
    }

    public void putInDDQ(LinkedList<Integer> deque, int value) {
        while (deque.size() > 0 && deque.peekLast() < value) {
            deque.pollLast();
        }
        deque.offerLast(value);
    }

    public static void main(String[] args) {
        int[] a = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        System.out.println(Arrays.toString(new LC239().maxSlidingWindow(a, k)));
    }
}
